package com.lw.leetcode.sort.b;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1477. 找两个和为目标值且不重叠的子数组
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/4 17:23
 */
public class MinSumOfLengths {

    public static void main(String[] args) {
        MinSumOfLengths test = new MinSumOfLengths();

        // 3
        int[] arr = {3, 1, 1, 1, 5, 1, 2, 1};
        int target = 3;

        // 2
//        int[] arr = {7, 3, 4, 7};
//        int target = 7;
        int i = test.minSumOfLengths(arr, target);
        System.out.println(i);
    }

    public int minSumOfLengths(int[] arr, int target) {
        List<Node> list = new ArrayList<>();
        int length = arr.length;
        int sum = arr[0];
        int st = 0;
        int end = 1;
        while (end < length) {
            if (sum == target) {
                list.add(new Node(end - st, st, end - 1));
                sum -= arr[st];
                st++;
            } else if (sum < target) {
                sum += arr[end];
                end++;
            } else {
                sum -= arr[st];
                st++;
            }
        }
        while (sum >= target) {
            if (sum == target) {
                list.add(new Node(end - st, st, end - 1));
                break;
            }
            sum -= arr[st];
            st++;
        }
        list.sort(Comparator.comparing(node -> node.count));
        int size = list.size();
        System.out.println(list);
        for (int i = 1; i < size; i++) {
            Node node = list.get(i);
            int a = node.st;
            int b = node.end;

            for (int j = 0; j < i; j++) {
                Node no = list.get(j);
                int a1 = no.st;
                int b1 = no.end;
                if (b < a1 || a > b1) {
                    return node.count + no.count;
                }
            }
        }
        return -1;
    }

    private class Node {
        private int count;
        private int st;
        private int end;

        @Override
        public String toString() {
            return "Node{" +
                    "count=" + count +
                    ", st=" + st +
                    ", end=" + end +
                    '}';
        }

        public Node(int count, int st, int end) {
            this.count = count;
            this.st = st;
            this.end = end;
        }
    }
}
